package 程序员面试金典;

/**
 * 面试题 04.04. 检查平衡性
 * 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
 *
 *
 * 示例 1:
 * 给定二叉树 [3,9,20,null,null,15,7]
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 * 返回 true 。
 * 示例 2:
 * 给定二叉树 [1,2,2,3,3,null,null,4,4]
 *       1
 *      / \
 *     2   2
 *    / \
 *   3   3
 *  / \
 * 4   4
 * 返回 false 。
 */
public class T04_04 {
    //解题思路 dfs 深度遍历 统计左右子数的深度
    private boolean ans = true;

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        dfs(root);
        return ans;

    }

    int dfs(TreeNode root) {

        if (root == null) {
            return 0;
        }
        //左子数的深度
        int l = dfs(root.left);
        //右子数的深度
        int r = dfs(root.right);
        //判断本节点是否平衡
        if (Math.abs(l - r) > 1) ans = false;
        //返回本节点的深度
        return Math.max(l, r) + 1;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
